package com.leetcode.剑指Offer;

import java.util.Arrays;

/**
 * 找出数组中重复的数字。
 * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
 * 数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

 * @author LZF
 *	
 *	思路：题目保证每个数都是0~n-1，并且2 <= n <= 100000。常规操作就是利用一个容器来存放这些值，遇到重复的就返回。
 *	利用这道题给的特性，不要申请额外的空间来完成：
 *	每个数都是0~n-1，则说明这些数都可以是这个数组的索引，从左往右遍历，就将这个位置上对应的值，作为索引，那索引位置上的值变为负数，作为标记。
 *	假设nums[0]=2,说明2这个数已经出现过了，就将nums[2]变为负数，下次遇到nums[i]=2的时候，如果判断nums[2]为负数，说明2重复出现了，将2返回。
 *	特殊情况：比如当nums[0]=2,就将nums[2]变为负数，但是nums[2]=0的时候，就不好标记，因为0变为负数还是0.
 *	根据题目的2 <= n <= 100000。我们就将每个数变为负数前加1，再变为负数，比如0就变为-1，3就变为-4等等。
 *	整体步骤：当遍历到i时：
 *	① 取nums[i]的值作为索引idx，如果idx<0，则我们要取变为负数之前的值，即idx=Math.abs(nums[i] + 1);
 *		如果idx>=0,idx不变。
 *	② 将nums[idx]加1之后再变为负数，表示idx这个数已经出现过了，nums[idx] = -(nums[idx]+1)
 */
public class Offer03数组中重复的数字 {
	
	public static void main(String[] args) {
		int[] nums = {2,3,1,4,0,5,3};
		System.out.println(findRepeatNumber(nums));
	}
	public static int findRepeatNumber(int[] nums) {
		for(int i = 0;i < nums.length;i++) {
			int idx;
			if(nums[i] < 0) {
				idx = Math.abs(nums[i] + 1);//取 变为负数前 的值
			}else{
				idx = nums[i];
			}
			//以上idx取得nums[i]位置上的值，说明idx出现过了，将其作为索引，把对应的位置加1再变为负数
			if(nums[idx] < 0) return idx;//如果该位置已经是负数了，说明idx是重复的
			nums[idx] = -nums[idx] - 1;
//			System.out.println(Arrays.toString(nums));
		}
        return -1;
    }
}
